---
title: Data Structure Basics pt.3
description: >
  Notes on lists.
categories: posts
tags: [data-structures, ruby]
---

<details markdown="1" id="table-of-contents">
<summary>
Table of Contents
</summary>

* TOC
{:toc}
</details>

## Review

Previously we talked about data structures in [general]({{site.url}}/posts/data-structure-basics-1){:rel="noopener"}.
Then we focused on [arrays]({{site.url}}/data-structure-basics-2){:rel="noopener"}.
Now it's time to cover lists, stacks, and queues.

## Lists

A list, like an array, is a kind of collection. That is because they both group
items together under one name.
The main difference between traditional arrays and traditional lists is in the
idea of direct access vs sequential access. This has to do with the way they are
stored in memory.
Another difference is in vocabulary. Whereas arrays contain data objects, lists
contain nodes. Nodes are nothing but the data object plus one or more pointers.
Pointers hold references to other nodes.

### Direct Access

We say that a data structure supports direct access when all of its elements are
allocated next to each other in memory. Arrays support direct access. That means
that as long as we know the index of an item we can find it almost instantly
regardless of the array's size.

### Sequential Access

Just like arrays are all about direct access, lists are all about sequential
access. Lists are collections of ordered items whose structure instead of being based on
an strict numeric index is based on a sequence of elements which don't have to
be stored in memory next to each other.

### Linked Lists

The sequence, or order, of a linked list is manage by each node. Nodes keep
references to nodes connected to them.

#### Singly Linked Lists

The nodes in this kind of lists only hold the reference to the next node.
Typically the last node's next-reference leads to Null.

- [Singly linked list](https://www.tutorialspoint.com/data_structures_algorithms/images/linked_list.jpg){:rel="nofollow noopener noreferrer"}

#### Doubly Linked Lists

Nodes in doubly linked lists hold references to both, the previous and next nodes.
This makes inserting and removing nodes a simpler task. Just like with singly
linked lists the last node's next-reference leads to Null and so does the first
node's previous-reference.

- [doubly linked list](https://www.tutorialspoint.com/data_structures_algorithms/images/doubly_linked_list.jpg){:rel="nofollow noopener noreferrer"}

#### Circular Doubly Linked Lists

The main difference between circular and common doubly linked lists is that
instead of having the first and last nodes point to Null, we point them at each
other. That is, the first node's previous-reference points to the last element of
the list. Likewise, the last node's next-reference points to the first node.

- [circular doubly linked list](https://www.tutorialspoint.com/data_structures_algorithms/images/doubly_circular_linked_list.jpg){:rel="nofollow noopener noreferrer"}

### Lists in Ruby

Ruby doesn't have a built-in implementation.

## Stacks

Stacks, like arrays and lists, are collections of items. The difference is
in the way they behave which is better described by the LIFO acronym; Last in,
first out, which is how regular stacks work.
Generally, stacks respond to three messages. `push`, to add to the top. `pop`, to
remove from the top only. `peek`, to check what the object at the top is
without removing it. Not all stacks implement the peek method.

- [stack operations](https://www.tutorialspoint.com/data_structures_algorithms/images/stack_representation.jpg){:rel="nofollow noopener noreferrer"}

Working with stacks should be even simpler than working with arrays and linked
lists because there is less we can do with it. It is intentionally limited.

### Stacks in Ruby

Even though Ruby doesn't have a built-in implementation for stacks we can loosely
emulate one with an array. Arrays in Ruby respond to `#push` and `#pop` the same
way stacks do. Keep in mind, though, that even when Ruby has a `#peek` method, it
doesn't behave as described above because ruby arrays are not stacks.

## Queues

Whereas stacks are last-in-first-out, queues are first-in-first-out. This means
that we can only add elements to the back of a queue, and we can only pick them
from the front. Queues are important for multithreads.
This is how we enqueue (add) items:

- [enqueue](https://www.tutorialspoint.com/data_structures_algorithms/images/queue_enqueue_diagram.jpg){:rel="nofollow noopener noreferrer"}

Here's the diagram for dequeue (remove)

- [dequeue](https://www.tutorialspoint.com/data_structures_algorithms/images/queue_dequeue_diagram.jpg){:rel="nofollow noopener noreferrer"}

### Priority Queues

This kind of queues allow us to specify a priority to the elements as we add them
to the queue. This way new objects can be added ahead of other already there.
If we add several items with the same priority they should follow FIFO.
Since defining priority can be tricky, we usually need to implement a comparison
function where we can define what we consider a higher, lower, or equal priority.

### Deque (Double-ended Queues)

This kind of queue allows us to add and remove objects from either end but never
from anywhere else. Hence, a deque behaves like both a stack and a queue.

### Queues in Ruby

Just like with stacks, Ruby doesn't have a built-in queue implementation. Yet,
we can use ruby arrays to get the same behavior as simple queues, as well as
deques. We use `push` for adding objects to the end of an array. And `#shift` for
picking the first object. If we need priority queues we need to implement them.

Do not confuse the queue behavior of an array with the Queue class which is meant
to be used as a way to synchronize communication between threads (Ruby Thread
objects).

### Before We Go

In this short article we covered some of the most fundamental data structures.
We also talked about how we can get similar behavior from Ruby's own array
implementation. Which should proof extremely useful to built custom data
structures. On the next article we'll talk about associative arrays. Cheers!
